Search for: All records

Motivated by the problem of estimating bottleneck capacities on the Internet, we formulate and study the problem of vantage point selection. We are given a graph G = (V, E) whose edges E have unknown capacity values that are to be discovered. Probes from a vantage point, i.e, a vertex v ∈ V, along shortest paths from v to all other vertices, reveal bottleneck edge capacities along each path. Our goal is to select k vantage points from V that reveal the maximum number of bottleneck edge capacities. We consider both a non-adaptive setting where all k vantage points are selected before any bottleneck capacity is revealed, and an adaptive setting where each vantage point selection instantly reveals bottleneck capacities along all shortest paths starting from that point. In the non-adaptive setting, by considering a relaxed model where edge capacities are drawn from a random permutation (which still leaves the problem of maximizing the expected number of revealed edges NP-hard), we are able to give a 1-1/e approximate algorithm. In the adaptive setting we work with the least permissive model where edge capacities are arbitrarily fixed but unknown. We compare with the best solution for the particular input instance (i.e. by enumerating all choices of k tuples), and provide both lower bounds on instance optimal approximation algorithms and upper bounds for trees and planar graphs. 

Sequential learning models situations where agents predict a ground truth in sequence, by using their private, noisy measurements, and the predictions of agents who came earlier in the sequence. We study sequential learning in a social network, where agents only see the actions of the previous agents in their own neighborhood. The fraction of agents who predict the ground truth correctly depends heavily on both the network topology and the ordering in which the predictions are made. A natural question is to find an ordering, with a given network, to maximize the (expected) number of agents who predict the ground truth correctly. In this paper, we show that it is in fact NP-hard to answer this question for a general network, with both the Bayesian learning model and a simple majority rule model. Finally, we show that even approximating the answer is hard. 

Abstract Optical vortices have the tremendous potential to increase data capacity by leveraging the extra degree of freedom of orbital angular momentum. On the other hand, anisotropic 2D materials are promising building blocks for future integrated polarization‐sensitive photonic and optoelectronic devices. Here, highly anisotropic third‐harmonic optical vortex beam generation is demonstrated with fork holograms patterned on ultrathin 2D germanium arsenide flakes. It is shown that the anisotropic nonlinear vortex beam generation can be achieved independent of the fork grating orientation with respect to the crystallographic orientation. Furthermore, 2D fork hologram is designed to generate multiple optical vortices having different topological charges with strong anisotropic responses. These results pave the way toward the advancement of 2D material‐based anisotropic nonlinear optical devices for future applications in photonic integrated circuits, optical communication, and optical information processing. 

Metric magnitude of a point cloud is a measure of its ``size. It has been adapted to various mathematical contexts and recent work suggests that it can enhance machine learning and optimization algorithms. But its usability is limited due to the computational cost when the dataset is large or when the computation must be carried out repeatedly (e.g. in model training). In this paper, we study the magnitude computation problem, and show efficient ways of approximating it. We show that it can be cast as a convex optimization problem, but not as a submodular optimization. The paper describes two new algorithms -- an iterative approximation algorithm that converges fast and is accurate in practice, and a subset selection method that makes the computation even faster. It has previously been proposed that the magnitude of model sequences generated during stochastic gradient descent is correlated to the generalization gap. Extension of this result using our more scalable algorithms shows that longer sequences bear higher correlations. We also describe new applications of magnitude in machine learning -- as an effective regularizer for neural network training, and as a novel clustering criterion. 

Abstract Detection and identification of chiral molecules are important for pharmaceutical industry, clinical analysis, and food analysis. Here, chiral molecular sensing based on spatially selective coupling between achiral metasurface and chiral molecules is demonstrated. The designed achiral metasurface exhibits strong optical chirality and electric field with dissymmetric distribution, and chiral molecules are selectively placed over the area with large optical chirality to form the coupled metasurface-molecule system with circular dichroism (CD) response for chiral molecular sensing. The CD spectra of the metasurface coupled with pure D-alanine enantiomer, L-alanine enantiomer and their mixtures are examined. The linear relationship between the peak CD value and the enantiomeric excess is demonstrated for the detection and identification of pure enantiomers and their mixtures. Furthermore, the CD response of the coupled system shows potential for the sensing of molar concentration of chiral molecules. Moreover, the effect of spatial location of molecules on the CD response is analyzed to show potential for position sensing of chiral molecules. These results of chiral molecular sensing with achiral metasurface offer new opportunities for advancing biomolecular sensing applications.